﻿//316.去除重复字母
//给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。
//需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
class Solution {
public:
    string removeDuplicateLetters(string s)
    {
        int arr[26];
        bool stack_arr[26];
        string sta;
        for (auto& e : s)
        {
            arr[e - 'a']++;
        }
        for (auto& e : s)
        {
            if (sta.empty() || (sta.back() < e && !stack_arr[e - 'a']))
            {
                sta.push_back(e);
                arr[e - 'a']--;
                stack_arr[e - 'a'] = 1;
            }
            else if (!stack_arr[e - 'a'])
            {
                while (!sta.empty() && sta.back() > e && arr[sta.back() - 'a'] > 0)
                {
                    stack_arr[sta.back() - 'a'] = 0;
                    sta.pop_back();
                }
                sta.push_back(e);
                stack_arr[e - 'a'] = 1;
                arr[e - 'a']--;
            }
            else if (arr[e - 'a'] == 1 && !stack_arr[e - 'a'])
            {
                sta.push_back(e);
                arr[e - 'a']--;
                stack_arr[e - 'a'] = 1;
            }
            else
            {
                arr[e - 'a']--;
            }
        }
        return sta;

    }
};